package net.flintx.array;

import java.util.Arrays;
import java.util.Stack;

/**
 * Created by flintx on 2018/1/10.
 */
public class ShortestUnsortedContinuousSubarray {
    public int findUnsortedSubarray(int[] nums) {
        if (nums.length <= 1)
            return 0;
        int[] sortedArray;
        sortedArray = Arrays.copyOf(nums, nums.length);
        Arrays.sort(sortedArray);
        int count = 0, start = Integer.MAX_VALUE, end = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if (sortedArray[i] != nums[i]) {
                count += 1;
                start = Math.min(start, i);
                end = Math.max(end, i);
            }
        }
        Arrays.sort(nums);
        return count == 0? 0: end - start + 1;
    }

    private static int betterMethod(int[] nums) {
        if (nums.length < 2)
            return 0;
        Stack<Integer> stack = new Stack<>();
        int leftBound = nums.length - 1, rightBound = 0;
        for (int i = 0; i < nums.length; i++) {
            if (!stack.empty()) {
                if (nums[i] >= nums[stack.peek()]) {
                    stack.push(i);
                } else {
                    leftBound = Math.min(leftBound, stack.pop());
                    i--;
                }
            } else {
                stack.push(i);
            }
        }
        stack.clear();
        for (int i = nums.length - 1; i >= 0; i--) {
            if (!stack.empty()) {
                if (nums[i] <= nums[stack.peek()]) {
                    stack.push(i);
                } else {
                    rightBound = Math.max(rightBound, stack.pop());
                    i++;
                }
            } else {
                stack.push(i);
            }
        }
        return rightBound - leftBound > 0? rightBound - leftBound + 1: 0;
    }

    private static int betterMethod2(int[] nums) {
        if (nums.length < 2)
            return 0;
        int start = -2, end = -1;
        int minValue = nums[nums.length - 1], maxValue = nums[0];
        for (int i = 1; i < nums.length; i++) {
            maxValue = Math.max(maxValue, nums[i]);
            minValue = Math.min(minValue, nums[nums.length - i - 1]);
            if (nums[i] < maxValue) {
                end = i;
            }
            if (nums[nums.length - i - 1] > minValue) {
                start = nums.length - i - 1;
            }
        }
        return end - start + 1;
    }

    public static void main(String[] args) {
        int[] nums = {2, 6, 4, 8, 10, 9, 15};
//        System.out.println(new ShortestUnsortedContinuousSubarray().findUnsortedSubarray(nums));
        System.out.println(betterMethod2(nums));
    }
}

// 2, 6, 4, 8, 10, 9, 15 => 0, 4, -2, 4, 2, -1, 6
// 2, 6, 4, 8, 3, 10, 9, 15 => 0, 4, -2, 4, -5, 7, -1, 6